package com.love.labuladong.sort.mergesort;



/**
 * 归并分治-小和问题
 */
public class MinSum {

    public static int minSum(int[] arr){
        return process(arr,0,arr.length - 1);
    }


    /**
     * 定义 ：arr[l...r] 返回题目中的小和问题，并给 arr 排序
     * @param arr
     * @param l
     * @param r
     * @return
     */
    public static int process(int[] arr,int l,int r){
        if(l == r){
            return 0;
        }
        int mid = l + ((r - l) >>> 1);

        return process(arr,l,mid) + process(arr,mid + 1,r) + marge(arr,l,mid,r);


    }

    private static int marge(int[] arr, int start, int mid, int end) {
        int ans = 0;
        // 这个地方是最精彩的
        for (int i = mid + 1,j = start,sum = 0; i <= end ; i++) {
            // j 是不会退的
            while (j <= mid && arr[j] < arr[i]){
                sum += arr[j];
                j++;
            }
            ans += sum;
        }

        // 左右排序
        int[] temp = new int[end - start + 1];
        int l = start;
        int r = mid + 1;
        int i = 0;
        while (l <= mid && r <= end){
            temp[i++] = arr[l] < arr[r] ? arr[l++] : arr[r++];
        }
        while (l <= mid){
            temp[i++] = arr[l++];
        }
        while (r <= end){
            temp[i++] = arr[r++];
        }
        for (int t : temp) {
            arr[start++] = t;
        }
        return ans;
    }


    public static void main(String[] args) {
        int[] nums = {1,3,5,2,4,6};
        int i = minSum(nums);
        System.out.println(i);
    }

}
